package sort;

/**
 *
 *
 *  希尔排序：直接插入升级版，
 *  增加一个gap系数，进行间隔分组排序，每个分组进行直接插入排序
 *  gap = gap / 3 + 1 ，gap依次变小 最后为1，由于经过前几次的插入排序
 *  序列已经大致正序了。
 *  当gap > 1 都是预排序，为了让数组更接近有序，只有当gap == 1 才是直接插入排序
 *  时间复杂度：O(NlogN) - O(N^2)
 *  平均时间复杂度O(N^1.3)
 *  空间复杂度：O(1)
 *  稳定性：不稳定，相同元素被划分到不同组排序，当前前后顺序变化
 *  数据敏感：数组越有序效率越高
 *
 *  实现：
 *
 */

public class ShellSort {


    static void asc(int[] arr){
        int n = arr.length;
        int gap = n;

        while (gap != 1){
            gap = gap / 3 + 1;
            //每次排序的起点
            for (int i = 0; i < gap; i++) {
                //插入排序
                for (int j = i+gap; j < n; j = j+gap){
                    int k = j - gap;
                    int x = arr[j];
                    while(k >= 0 && arr[k] > x){
                        arr[k+gap] = arr[k];
                        k -= gap;
                    }
                    arr[k+gap] = x;
                }
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 3,5,1,10,6,5,4};
        asc(arr);
        for (int i : arr) {
            System.out.printf("%d ", i);
        }
    }
}
